/*
Copyright 2008, 2009 Joonas Lehtolahti

This file is part of Shared Datatypes and Utilities.

Shared Datatypes and Utilities is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

Shared Datatypes and Utilities is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License
along with Shared Datatypes and Utilities.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "linkedlist.h"

/**
 * LLcreate
 *  Creates a new LinkedList structure
 *
 * Parameters:
 *  Nothing
 *
 * Returns:
 *  Pointer to the new LinkedList
 */
DLLEXPORT(LinkedList*) LLcreate(void) {
	LinkedList *r = (LinkedList*)dmalloc(sizeof(LinkedList));
	r->first = NULL;
	r->last = NULL;
	r->nodes = 0;
	return r;
}

/**
 * LLdelete
 *  Deletes a LinkedList structure freeing memory
 *
 * Parameters:
 *  l         pointer to the LinkedList
 *  freefunc  pointer to function used to free the contents
 *
 * Returns:
 *  Nothing
 */
DLLEXPORT(void) LLdelete(LinkedList *l, FREEFUNC *freefunc) {
	if (l) {
		ListNode *n = l->first;
		ListNode *n2;
		while ((n2=n)!=NULL) {
			if (freefunc) {
				freefunc(n->x);
			}
			n = n->next;
			dfree(n2);
		}
		dfree(l);
	}
}

/**
 * LLaddFirst
 *  Adds an element to the beginning of a linked list
 * 
 * Parameters:
 *  l  pointer to the list to add the element to
 *  x  pointer to the element to be added
 * 
 * Returns:
 *  the pointer to the ListNode object or NULL if failed
 */
DLLEXPORT(ListNode*) LLaddFirst(LinkedList* l,void* x) {
	ListNode *n = (ListNode*)dmalloc(sizeof(ListNode));
	if (!n) return NULL;
	n->x=x;
	n->next=l->first;
	n->prev=NULL;
	n->list = l;
	if (l->first) l->first->prev=n;
	l->first=n;
	if (!(l->last)) l->last=n;
	l->nodes++;
	return n;
}

/**
 * LLaddLast
 *  Adds an element to the end of a linked list
 * 
 * Parameters:
 *  l  pointer to the list to add the element to
 *  x  pointer to the element to be added
 * 
 * Returns:
 *  the pointer to the ListNode object or NULL if failed
 */
DLLEXPORT(ListNode*) LLaddLast(LinkedList* l,void* x) {
	ListNode *n = (ListNode*)dmalloc(sizeof(ListNode));
	if (!n) return NULL;
	n->x=x;
	n->prev=l->last;
	n->next=NULL;
	n->list=l;
	if (l->last) l->last->next=n;
	l->last=n;
	if (!(l->first)) l->first=n;
	l->nodes++;
	return n;
}

/**
 * LLaddBefore
 *  Adds an element before a list node
 * 
 * Parameters:
 *  n  pointer to the list node before which the element is added
 *  x  pointer to the element to be added
 * 
 * Returns:
 *  the pointer to the new ListNode object or NULL if failed
 */
DLLEXPORT(ListNode*) LLaddBefore(ListNode* n,void* x) {
	ListNode *n2;
	if (!n) return NULL;
	n2 = (ListNode*)dmalloc(sizeof(ListNode));
	n2->x = x;
	n2->list = n->list;
	n2->prev = n->prev;
	if (!n2->prev) n2->list->first = n2;
	n2->next = n;
	n->prev = n2;
	n2->list->nodes++;
	return n2;
}

/**
 * LLaddAfter
 *  Adds an element after a list node
 * 
 * Parameters:
 *  n  pointer to the list node after which the element is added
 *  x  pointer to the element to be added
 * 
 * Returns:
 *  the pointer to the new ListNode object or NULL if failed
 */
DLLEXPORT(ListNode*) LLaddAfter(ListNode* n,void* x) {
	ListNode *n2;
	if (!n) return NULL;
	n2 = (ListNode*)dmalloc(sizeof(ListNode));
	n2->x = x;
	n2->list = n->list;
	n2->next = n->next;
	if (!n2->next) n2->list->last = n2;
	n2->prev = n;
	n->next = n2;
	n2->list->nodes++;
	return n2;
}

/**
 * LLdelNode
 *  Removes an element from a linked list
 * 
 * Parameters:
 *  n  pointer to the listnode to be removed
 * 
 * Returns:
 *  pointer to the element or
 *  NULL if failed
 */
DLLEXPORT(void*) LLdelNode(ListNode *n) {
	void *x;
	if (!n) return NULL;
	x = n->x;
	if (n->prev) n->prev->next = n->next;
	else n->list->first = n->next;
	if (n->next) n->next->prev = n->prev;
	else n->list->last = n->prev;
	n->list->nodes--;
	dfree(n);
	return x;
}

/**
 * LLdelFirst
 *  Removes an element from the beginning of a linked list
 * 
 * Parameters:
 *  l  pointer to the list from which the element is to be removed
 * 
 * Returns:
 *  pointer to the element or
 *  NULL if failed
 */
DLLEXPORT(void*) LLdelFirst(LinkedList* l) {
	void *x;
	ListNode *n;
	if (!l) return NULL;
	n = l->first;
	if (!n) return NULL;
	l->first=n->next;
	if (n->next) n->next->prev=NULL;
	else l->last=NULL;
	x = n->x;
	dfree(n);
	l->nodes--;
	return x;
}

/**
 * LLdelLast
 *  Removes an element from the end of a linked list
 * 
 * Parameters:
 *  l  pointer to the list from which the element is to be removed
 * 
 * Returns:
 *  pointer to the element or
 *  NULL if failed
 */
DLLEXPORT(void*) LLdelLast(LinkedList* l) {
	void *x;
	ListNode *n;
	if (!l) return NULL;
	n=l->last;
	if (!n) return NULL;
	l->last=n->prev;
	if (n->prev) n->prev->next=NULL;
	else l->first=NULL;
	x = n->x;
	dfree(n);
	l->nodes--;
	return x;
}

/**
 * LLmerge (LinkedList *first, LinkedList *second)
 *   Merges (appends) seconds list into first one and destroys the seconds one
 * 
 * Parameters:
 *   first   the list into which the second list is appended to
 *   second  the list which is appended to first and and then deleted
 * 
 * Returns:
 *  pointer to first
 *  NULL if failed
 */
DLLEXPORT(LinkedList*) LLmerge(LinkedList *first, LinkedList *second) {
	ListNode *n;
	if (!first) return NULL;
	if (!second) return NULL;
	first->nodes += second->nodes;
	n = first->last->next = second->first;
	second->first->prev = first->last;
	first->last = second->last;
	dfree(second);
	while (n) {
		n->list = first;
		n = n->next;
	}
	return first;
}
